package com.aqie.medium.binarySearch;

import java.util.HashSet;

/**
 * 287 n+1 整数只有一个数重复 这个数可能不止重复一次
 */
public class FindDuplicate {
    /**
     * hash
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        int ans = -1;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            if (!set.add(nums[i])) ans = nums[i];
        }
        return ans;
    }

    /**
     * 双指针（最优解）
     * @param nums
     * @return
     */
    public int findDuplicate2(int[] nums) {
        int fast = 0, slow = 0;
        while (true){
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (slow == fast){
                fast = 0;
                while (nums[slow] != nums[fast]){
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return nums[slow];
            }
        }
    }

    /**
     * 二分查找
     * @param nums
     * @return
     */
    public int findDuplicate3(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high){
            int mid = low + ((high - low) >> 1);
            int count = 0;
            for (int num : nums){
                if (num <= mid ) count++;
            }
            if (count <= mid) low = mid + 1;
            else{
               high = mid;
            }
        }
        return low;
    }
}
